A conventional method of generating check matrixes for LDPC codes will be explained below. In a conventional LDPC code encoding/decoding system, a communication apparatus at a sending side has an encoder and a modulator. On the other hand, an apparatus at a receiving side has a demodulator and a decoder. Prior to explanation of the conventional method of generating check matrixes for LDPC codes, flows of encoding and decoding using LDPC codes are explained first.
At the sending side, the encoder generates a check matrix H according to the conventional method described later. Then, a generator matrix G is obtained based on the following condition.G: k×n matrix (k: information length, n: code word length)GHT=0 (T denotes transposition)
The encoder then receives a message (m1 m2 . . . mk) of an information length k, and generates a code word C using the generator matrix G.
                    C        =                              (                                          m                1                            ⁢                              m                2                            ⁢                                                          ⁢              …              ⁢                                                          ⁢                              m                k                                      )                    ⁢          G                                        =                              (                                          c                1                            ⁢                              c                2                            ⁢                                                          ⁢              …              ⁢                                                          ⁢                              c                n                                      )                    ⁢                      (                                          where                ⁢                                                                  ⁢                                                      H                    ⁡                                          (                                                                        c                          1                                                ⁢                                                  c                          2                                                ⁢                                                                                                  ⁢                        …                        ⁢                                                                                                  ⁢                                                  c                          n                                                                    )                                                        T                                            =              0                        )                              
The modulator subjects the generated code word C to a digital modulation such as binary phase shift keying (BPSK), quadrature phase shift keying (QPSK), and multi-valued quadrature amplitude modulation (QAM), and sends the modulated signal.
At the receiving side on the other hand, the demodulator receives the modulated signal via the channel, and subjects it to a digital demodulation such as BPSK, QPSK, and multi-valued QAM. Then the decoder performs an iterative decoding by “sum-product algorithm” with respect to the demodulated result that is LDPC-coded, and outputs an estimated result (corresponding to the original m1 m2 . . . mk).
A conventional method of generating check matrixes for LDPC codes is explained below. As a check matrix for LDPC codes, the following matrix is proposed in “R. G. Gallager, “Low-Density Parity Check Codes”M.I.T Press, Cambridge. Mass., 1963” (see FIG. 16).
The matrix shown in FIG. 16 is a binary matrix of “1” and “0”, in which a part of “1” is hatched. Other parts are all “0”. In this matrix, the number of “1”s in one row (expressed as a row weight) is equal to 4, and the number of “1”s in one column (expressed as a column weight) is equal to three. All columns and rows have respective uniform weights. Thus, it is generally called a “regular-LDPC code”. In the codes in the Non-patent Literature 1, the matrix is separated into three blocks, for example, and the second and the third blocks are subjected to random permutation, as shown in FIG. 16.
Because the random permutation has no certain rule, it is required to execute a time-consuming search by a computer to find codes with a better characteristic.
It is proposed in Y. Kou, S. Lin, and M. P. C. Fossorier, “Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery”, ISIT 2000, pp. 200, Sorrento, Italy, Jun. 25-30, 2000 a method using Euclidean geometry codes as the LDPC codes that exhibit a relatively stable and satisfactory characteristic and can definitely generate a matrix without the use of the computer search. This method explains the “regular-LDPC code” consisting of regular ensembles.
The second literature proposes a method of generating a check matrix for LDPC codes using Euclidean geometry codes EG (2, 26) as a kind of finite geometric codes. This method achieves a characteristic that is located closely but 1.45 decibels away from the Shannon limit at an error rate of 10−4. FIG. 17 is a diagram of a configuration of Euclidean geometry codes EG (2, 22), which has a structure of “Regular-LDPC Codes” with row and column weights of 4 and 4, respectively.
Euclidean geometry codes EG (m, 2s) have a characteristic defined as follows:Code length: n=22s−1Redundant bit length: n−k=3s−1Information length: k=22s−3sMinimum distance: dmin=2s+1Density: r=2s/(22s−1).
As can be seen from FIG. 17, Euclidean geometry codes have a structure with a cyclically sifted location of “1” in each row from an adjacent row. This structure can characteristically configure codes easily and definitely.
The check matrix generating method in the second literature further includes changing row and column weights based on the Euclidean geometry codes to extend rows and columns, if necessary. For example, when a column weight in EG (2, 22) is separated into halves, in the second literature, every other one of four weights located in one column is separated into two groups. FIG. 18 is a diagram of an exemplary regular separation of the column weight from 4 into 2.
On the other hand, M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation”, Proceedings of 1998 IEEE International Symposium on Information Theory, pp. 171, Cambridge, Mass., Aug. 16-21, 1998 has reported that “irregular-LDPC codes” have a better characteristic than that of “Regular-LDPC Codes”. This is theoretically analyzed in T. J. Richardson and R. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding”, IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 599-618, February 2001 and S.-Y. Chung, T. J. Richardson, and R. Urbanke, “Analysis of Sum-Product Decoding of Low-Density Parity-Check Codes Using a Gaussian Approximation”, IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 657-670, February 2001. The “irregular-LDPC codes” represent such LDPC codes that have non-uniformity in either or both of row and column weights.
Particularly, in the fifth literature, a “Sum-Product Algorithm” for LDPC codes is analyzed on the assumption that a log likelihood ratio (LLR) between an input and an output at an iterative decoder can be approximated in a Gaussian distribution, to derive a satisfactory ensemble of row and column weights.
According to the conventional method of generating check matrixes for LDPC codes disclosed in the fifth literature, however, the number of “1” points in a row (corresponding to a degree distribution of variable nodes described later) and the number of “1” points in a column (corresponding to a degree distribution of check nodes described later) are both employed as variables to derive the degree distribution of variable nodes and the degree distribution of check nodes that can maximize the following equation (1) (rate: coding rate). In other words, a linear programming is employed to search an ensemble that minimizes a Signal to Noise Ratio (SNR).
                    rate        =                  1          -                                                    ∫                0                1                            ⁢                              ρ                ⁡                                  (                  x                  )                                                                                    ∫                0                1                            ⁢                              λ                ⁡                                  (                  x                  )                                                                                        (        1        )            
Therefore, a problem arises that a check matrix derived from the maximum of the “rate” has a flux and unstable characteristic. In addition, the conventional method of generating check matrixes for LDPC codes iteratively executes the derivation of the degree distribution of variable nodes and the derivation of the degree distribution of check nodes over certain times. Therefore, a problem arises that it takes time to some extent for searching.
The present invention has been achieved in consideration of the above problems, and accordingly has an object to provide a method of generating check matrixes for LDPC codes having satisfactory performance capable of easily searching a definite and characteristic stabilized check matrix for LDPC codes corresponding to an optimal ensemble, and a check matrix generating apparatus.